#include <iostream>

using std::cout;

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode(int val):val(val),next(nullptr){}
};

class Soluction
{
public:
    static ListNode* swapPairs(ListNode* head) 
    {
        ListNode* dummyNode = new ListNode(-1); // 虚拟头结点
        dummyNode->next = head;

        ListNode* first = dummyNode;
        ListNode* second = first->next;
        while(second != nullptr && second->next != nullptr)
        {
            ListNode* tmp = second->next->next;
            first->next = second->next;
            second->next->next = second;
            second->next = tmp;

            first = second;
            second = first->next;
        }

        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};

int main(int argc, char const *argv[])
{
    ListNode* head = new ListNode(1);
    for(int i = 0;i < 5;++ i)
    {
        ListNode* newNode = new ListNode(i + 2);
        newNode->next = head->next;
        head->next = newNode;
    }
    ListNode* cur = head;
    while (cur != nullptr)
    {
        cout << cur->val;
        cur = cur->next;
    }


    cout << "\n";
    cur = Soluction::swapPairs(head);
    while (cur != nullptr)
    {
        cout << cur->val;
        cur = cur->next;
    }
    getchar();
    return 0;
}
